1.Графи, різновиди графів та дії над ними.
1.1. Графом EMBED Equation.3 називається пара непустої множини EMBED Equation.3 та відображення EMBED Equation.3 в ній. Інакше: граф EMBED Equation.3 складається з множини EMBED Equation.3 та невпорядкованих пар EMBED Equation.3 з множини EMBED Equation.3 – вершин графа.
Пара, EMBED Equation.3 ; EMBED Equation.3 і EMBED Equation.3 називається ребром графа EMBED Equation.3 , причому говорять, що EMBED Equation.3 та EMBED Equation.3 – суміжні вершини, EMBED Equation.3 , а ребро EMBED Equation.3 інцендентне вершині EMBED Equation.3 і вершині EMBED Equation.3 . Якщо в EMBED Equation.3 ребра EMBED Equation.3 є в одній і тій же вершині, то вони називаються суміжними ребрами.
Граф з EMBED Equation.3 вершинами та EMBED Equation.3 ребрами називається EMBED Equation.3 графом ; граф (1,0) – тривіальний і ребро, що з’єднує точку з собою називається петлею.
Типи графів:
1. Мультиграф – граф, що не містить петель, але пара вершин в якому з’єднується кілька раз – кратні ребра.
2. Псевдограф – граф, в якому допускається і петля, і кратні ребра. EMBED Equation.3
3. Орієнтований граф (орграф) – граф EMBED Equation.3 , в якому EMBED Equation.3 є множиною впорядкованих пар вершин із EMBED Equation.3 . Елементи із EMBED Equation.3 називаються орієнтованими ребрами або дугами. Дуги виду EMBED Equation.3 та EMBED Equation.3 - називаються симетричними дугами.
4. Направлений граф – орграф, що не має симетричних дуг.
5. Граф називається поміченим або перенумерованим, якщо його вершини відрізняються деякими проміжками, індексами EMBED Equation.3 .
6. Підграф графа EMBED Equation.3 , EMBED Equation.3 ; EMBED Equation.3 , EMBED Equation.3 .
7. Якщо EMBED Equation.3 - підграф EMBED Equation.3 , то EMBED Equation.3 називається надграфом для EMBED Equation.3 .
8. Частинний граф (основний граф) – підграф, що містить всі вершини графа.
9. Породженим множиною вершин EMBED Equation.3 підграф EMBED Equation.3 називається максимальним для EMBED Equation.3 з множиною EMBED Equation.3 ; в EMBED Equation.3 вершини суміжні тоді і тільки тоді, коли вони суміжні в EMBED Equation.3 . На введені поняття покажемо кілька прикладів.
SHAPE \* MERGEFORMAT 1) EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
SHAPE \* MERGEFORMAT EMBED Equation.3
граф породжений частинний
підграф граф
2) EMBED Equation.3 – підграф EMBED Equation.3 , що не містить вершини EMBED Equation.3 . Це максимальний підграф EMBED Equation.3 , що не містить вершини EMBED Equation.3 .
3) EMBED Equation.3 – частинний підграф без ребра EMBED Equation.3 , він є максимальним підграфом без ребра EMBED Equation.3 .
Процес видалення вершини EMBED Equation.3 та ребра EMBED Equation.3 графа EMBED Equation.3 показано на рисунку.
SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
EMBED Equation.3
4) EMBED Equation.3 , де EMBED Equation.3 не суміжні в EMBED Equation.3 , утворює найменший надграф для EMBED Equation.3 , що містить ребро EMBED Equation.3 .
1.2. Два графи EMBED Equation.3 і EMBED Equation.3 називаються ізоморфними, EMBED Equation.3 , якщо між множинами їх вершин існує взаємно-однозначна відповідність, що зберігає суміжність, наприклад EMBED Equation.3 .
SHAPE \* MERGEFORMAT EMBED Equation.3
, SHAPE \* MERGEFORMAT EMBED Equation.3
, SHAPE \* ...
